public class Test {
    /*
    被围绕的区域
    class Solution {
    int[] dx = { 0, 0, 1, -1 };
    int[] dy = { 1, -1, 0, 0 };

    int m, n;
    boolean[][] vis;

    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        vis = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    if (board[i][j] == 'O' && !vis[i][j]) {
                        // 都标记为其他字符 ?
                        bfs(board, i, j);
                    }
                }
            }
        }

        // 遍历
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] != '?') {
                    board[i][j] = 'X';
                } else {
                    board[i][j] = 'O';
                }
            }
        }
    }

    void bfs(char[][] board, int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { i, j });
        vis[i][j] = true;
        board[i][j] = '?';

        while (!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k];
                int y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n
                        && board[x][y] == 'O' && !vis[x][y]) {
                    q.offer(new int[] { x, y });
                    board[x][y] = '?';
                    vis[x][y] = true;
                }
            }
        }
    }
}

    岛屿的最大面积
    class Solution {
    // 设置偏移量
    int[] dx = { 0, 0, 1, -1 };
    int[] dy = { 1, -1, 0, 0 };

    // 记录岛屿的面积
    boolean[][] vis;
    int m, n;

    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        vis = new boolean[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 找到一块岛屿
                if (grid[i][j] == 1 && vis[i][j] == false) {
                    // 计算面积
                    max = Math.max(max, bfs(grid, i, j));
                }
            }
        }
        return max;
    }

    int bfs(int[][] grid, int i, int j) {
        int count = 1;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { i, j });
        while (!q.isEmpty()) {

            int[] t = q.poll();
            int a = t[0], b = t[1];
            vis[a][b] = true;
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n
                        && grid[x][y] == 1 && vis[x][y] == false) {
                    q.offer(new int[] { x, y });
                    vis[x][y] = true;
                    count++;
                }
            }
        }

        return count;
    }
}

    全排列
    class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;

    public List<List<Integer>> permute(int[] nums) {

        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        dfs(nums);
        return ret;
    }

    void dfs(int[] nums) {
        if (nums.length == path.size()) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (check[i] == false) {
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                // 回退
                check[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}
    两数相加
    class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //构建虚拟节点
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        int ret = 0;
        while (l1 != null || l2 != null || ret != 0) {
            // + l1
            if (l1 != null) {
                ret += l1.val;
                l1 = l1.next;
            }
            // + l2
            if (l2 != null) {
                ret += l2.val;
                l2 = l2.next;
            }
            //连接新结果
            cur.next = new ListNode(ret % 10);
            cur = cur.next;
            ret /= 10;

        }

        return newHead.next;
    }
}
     */
}
